#include <memory>
#include <functional>
#include <iostream>

using namespace std;

template <class T, class CompareFunction = less<T>>
class LeBST
{
private:
	struct LeBSTNode
	{
		T data;
		LeBSTNode * parent;
		shared_ptr<LeBSTNode> left, right;

		LeBSTNode(T & x) : data(x), parent(NULL), left(NULL), right(NULL) {}
		
		LeBSTNode(LeBSTNode const &) { throw logic_error( "can't copy LeBSTNode" ); }

		~LeBSTNode() { cout << "deleting : " << data << endl; }
	};

public:

	LeBST(CompareFunction cmprr) : root(NULL), comparer(cmprr) {}

	LeBST() : root(NULL) {}

	bool insert(T x)
	{
		if (root == NULL) // adding first element into tree
		{
			root = shared_ptr<LeBSTNode>(new LeBSTNode(x));
			return true;
		}
		else 
		{
			LeBSTNode * node = &*root;
			while (true) // find the right place for the new item
			{
				if (comparer(x, node->data))
				{
					// go left
					if (node->left != NULL) node = &(*node->left); // deeper and deeper :)
					else
					{
						// create new node, link its parent ptr, and its parent-child ptr
						LeBSTNode * newNode = new LeBSTNode(x);
						node->left = shared_ptr<LeBSTNode>(newNode);
						newNode->parent = node;
						return true;
					}
				}
				else if (comparer(node->data, x)) 
				{
					// go right
					if (node->right != NULL) node = &(*node->right); // deeper and deeper :)
					else
					{
						// create new node, link its parent ptr, and its parent-child ptr
						LeBSTNode * newNode = new LeBSTNode(x);
						node->right = shared_ptr<LeBSTNode>(newNode);
						newNode->parent = node;
						return true;
					}
				}
				else return false; // item already exists. allow no duplicates.
			}
		}
		return false; // shouldn't ever reach this line
	}

	bool find(T x) { return findNode(x); }

	bool erase(T x) { return erase(findNode(x)); }

	T & min() { return (min(&*root))->data; }

	T & max() { return (max(&*root))->data; }

private:
	CompareFunction comparer;
	shared_ptr<LeBSTNode> root;

	LeBSTNode * findNode(T x)
	{
		LeBSTNode * node = &*root;
		while (true)
		{
			if (node == NULL) return NULL;
			else if (comparer(x, node->data)) node = &(*node->left);
			else if (comparer(node->data, x)) node = &(*node->right);
			else return node;
		}
		return NULL;
	}

	bool erase(LeBSTNode * found)
	{
		if (found == NULL) return false;

		LeBSTNode * parent = found->parent;

		if (found->left == NULL && found->right == NULL) // has no children
		{
			if (parent == NULL) root = NULL; // erasing the only element from the tree
			else
			{
				if (&(*parent->left) == found) parent->left = NULL;
				else parent->right = NULL;
			}
		}
		else if (found->left != NULL && found->right == NULL) // has only left child
		{
			found->left->parent = parent; // bind childs parent to one node upwards
			if (parent == NULL) root = found->left;
			else
			{
				if (&(*parent->left) == found) parent->left = found->left;
				else parent->right = found->left;
			}
		}
		else if (found->left == NULL && found->right != NULL) // has only right child
		{
			found->right->parent = parent; // bind childs parent to one node upwards
			if (parent == NULL) root = found->right;
			else
			{
				if (&(*parent->left) == found) parent->left = found->right;
				else parent->right = found->right;
			}
		}
		else
		{
			LeBSTNode * succ = min(&(*found->right)); // find its min
			found->data = succ->data; // copy data

			return erase(succ); // since the data is already copied, simply delete the min
		}
		return true;
	}

	LeBSTNode * min(LeBSTNode * from)
	{
		LeBSTNode * node = from;
		while (node->left != NULL) node = &(*node->left);
		return node;
	}

	LeBSTNode * max(LeBSTNode * from)
	{
		LeBSTNode * node = from;
		while (node->right != NULL) node = &(*node->right);
		return node;
	}
};